package com.tucc.hello.leetcode.no1_400.no1_200.no21_40.no34;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1};
        int target = 1;
        int[] result = solution.searchRange(nums, target);
        System.out.println(result[0] + " " + result[1]);
    }

    public int[] searchRange(int[] nums, int target) {
        int l = -1;
        int r = -1;
        int len = nums.length - 1;
        int index = binarySearch(nums, 0, len, target);
        if (index != -1) {
            l = r = index;
            int lIndex = l;
            do {
                lIndex = binarySearch(nums, 0, lIndex - 1, target);
                if (lIndex != -1) {
                    l = lIndex;
                }
            } while (lIndex != -1);


            int rIndex = r;
            do {
                rIndex = binarySearch(nums, rIndex + 1, len, target);
                if (rIndex != -1) {
                    r = rIndex;
                }
            } while (rIndex != -1);
        }
        return new int[]{l, r};
    }


    public int binarySearch(int[] nums, int l, int r, int target) {
        if (l > r || l < 0) {
            return -1;
        }
        if (l == r) {
            return nums[l] == target ? l : -1;
        }
        int mid = (l + r) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            return binarySearch(nums, l, mid - 1, target);
        } else {
            return binarySearch(nums, mid + 1, r, target);
        }
    }


}
